import java.util.*;

public class test {
    // leetcode 397.整数替换
    // 1.dfs (6ms)
    public int integerReplacement1(int n) {
        return dfs1(n,0);
    }
    public int dfs1(long num,int n){
        if(num == 1) return n;
        n = n + 1;
        if(num % 2 == 0){
            return dfs(num / 2,n);
        }else {
            return Math.min(dfs(num + 1,n),dfs(num - 1,n));
        }
    }
    // 2.记忆化搜索 (1ms)
    public HashMap<Long,Integer> memo;
    public int integerReplacement2(int n) {
        memo = new HashMap<>();
        return dfs2(n,0);
    }
    public int dfs2(long num,int n){
        if(memo.containsKey(num)){
            return n + memo.get(num);
        }
        if(num == 1) {
            return n;
        }
        n = n + 1;
        int steps;
        if(num % 2 == 0){
            steps = dfs(num / 2,n);
        }else {
            steps = Math.min(dfs(num + 1,n),dfs(num - 1,n));
        }
        memo.put(num,steps - n + 1);
        return steps;
    }
    // 3.贪心 (0ms)
    // 解法1和2中,在num为奇数时,分别尝试+1和-1,然后取最小的操作数
    // 而贪心可以"直接知道最小的操作数"
    public int integerReplacement(int n) {
        return dfs(n,0);
    }
    public int dfs(long num,int n){
        if(num == 1) return n;
        n = n + 1;
        if(num % 2 == 0){
            return dfs(num / 2,n);
        }else {
            // 取当前num二进制的上一位
            // 如果上一位为1,则取num+1(进位使多个位变成0) (0是特殊情况)
            // 如果上一位为0,则取num-1(避免进位1)
            if((num / 2) % 2 == 1 && num != 3){
                return dfs(num + 1,n);
            }else {
                return dfs(num - 1,n);
            }
        }
    }
    // leetcode 354.俄罗斯套娃信封问题
    // 1. 排序数组 -> 最长递增子序列问题(dp)
    public int maxEnvelopes1(int[][] envelopes) {
        int n = envelopes.length;
        // 使信封以宽度进行升序排序
        Arrays.sort(envelopes, Comparator.comparing(a -> a[0]));
        // 由于宽度已经有序,则找出高度中的"最长严格递增子序列"即可
        int[] dp = new int[n + 1];
        Arrays.fill(dp,1);
        int max = 0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < i;j++){
                // 注意:严格递增,需要判断高度不同
                if(envelopes[j - 1][0] != envelopes[i - 1][0] && envelopes[j - 1][1] < envelopes[i - 1][1]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }
    // 2. 动态规划 + 贪心优化(二分)
    // 和最长递增子序列问题类似,每次与上个子序列拼接时
    // 我们需要找到能够拼接的子序列中,长度最长的.
    // 而为了能选择的子序列尽可能多,应该使每个子序列结尾尽可能小
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        // 使信封以宽度进行升序排序
        // 如果宽度相同,以高度降序排序
        Arrays.sort(envelopes, (v1,v2) -> {
            if(v1[0] != v2[0]){
                return v1[0] - v2[0];
            }else {
                return v2[1] - v1[1];
            }
        });
        // 下标代表(长度为i的子序列的最小末尾值)
        int[] dp = new int[n + 1];
        // 当dp[i] = -1时,代表不存在该长度的子序列
        Arrays.fill(dp,-1);
        int left = 0;
        int right = 0;
        int max = 1;
        dp[1] = envelopes[0][1];
        for(int i = 2;i <= n;i++){
            int temp = envelopes[i - 1][1];
            left = 0;
            right = i - 1;
            // 1 1 2 4 4 4 5 6 -1
            while(left < right){
                int mid = left + (right - left + 1) / 2;
                if(dp[mid] == -1 || dp[mid] > temp){
                    right = mid - 1;
                }else {
                    left = mid;
                }
            }
            // 如果信封高度相同,则无法摆放(严格递增)
            if(dp[left] == temp) continue;
            if(dp[left + 1] == -1){
                dp[left + 1] = temp;
            }else {
                dp[left + 1] = Math.min(temp,dp[left + 1]);
            }
            max = Math.max(max,left + 1);
        }
        return max;
    }
}
